1. Field of the Invention
The present invention relates to a decoder circuit for decoding data compressed by using a LZ 77 method (Lempel-Ziv 77 method), for example, and particularly to a decoder circuit and a decoding method which can make decoding processing become faster.
2. Description of the Related Art
A LZ 77 method exists as a kind of dictionary type data compression algorithms. The LZ77 method is used in data compressing and decoding circuits provided within various kinds of data recording apparatus such as an ALDC (Adaptive Lossless Data Compression) encoder and an ALDC decoder within an AIT format tape drive, an S-AIT format tape drive or an LTO format tape drive.
A data compression principle of the LZ77 method will be described. That is, a last character string of a predetermined size of character strings (data strings) that have been inputted in the past is registered in a dictionary (history buffer), a match character string of a newly inputted character string (that is, a character string to be compressed) is retrieved from the dictionary and the newly inputted character string is replaced with address information of the match character string. This dictionary is not a static type dictionary but it is updated so as to remove an old character string by adding the character string just before the character string to be compressed in accordance with a progress of data compression. Hence, this dictionary is called a “sliding dictionary”.
FIG. 1 of the accompanying drawings is a schematic diagram showing an example of the manner in which data is compressed by the above-mentioned LZ77 method. Although it has been customary that the ordinary dictionary is 512 bytes, 1024 bytes or 2048 bytes in size, this sliding type dictionary is 16 bytes in size for simplicity of explanation. As shown in FIG. 1, a last character string “ABCCAB . . . BCC” (each of the characters A, B and C is one byte) of 16 characters of character strings that had been inputted in the past is registered as a dictionary. The character “A” that was inputted 16 bytes before is assigned an address 0, the character “B” that was inputted 15 bytes before is assigned an address 1 and the character “C” that was inputted one byte before is assigned an address 15.
When the newly inputted character string is “ABCA”, for example, a character string of addresses 9 to 12 is matched with “ABCA” by the retrieval processing. Accordingly, in this case, the address 12 is outputted as a match address (address defined as the end address of the match character string). Then, in the end, the character string “ABCA” of 4 bytes is compressed to 2 bytes by transforming the character string “ABCA” into a code word (Copy Pointer, Match Count=4 and Match Address=9) indicating a match address length 4 and a leading address 9.
When the thus compressed data is decoded, referring to this dictionary in the opposite manner, the code word (Copy Pointer, Match Count=4 and Match address=9) is transformed into the character string “ABCA”. In that case, as the processing opposite to the processing in which the dictionary is updated when data is compressed, the dictionary used upon compressing may be restored by rewriting characters in the dictionary in accordance with a progress of decoding processing.
FIGS. 2 to 6 are respectively schematic diagrams showing the manner in which compressed data are decoded, from a standpoint of elapse of time, in association with the dictionary shown in FIG. 1. First, as shown in FIG. 2, a dictionary address 9 (Match Address=9 indicated by a code word) is designated as a read address radr and a dictionary address 2 is designated as a write address wadr. Then, as shown in FIG. 3, a character “A” is read out from the address 9 and this character “A” is written again in the address 2, whereafter addresses 10 and 3 are designated as the read address radr and the write address wadr, respectively.
Subsequently, as shown in FIG. 4, a character “B” is read out from the address 10 and this character “B” is written again in the address “3”, whereafter addresses 11 and 4 are designated as the read address radr and the write address wadr, respectively.
Subsequently, as shown in FIG. 5, a character “C” is read out from the address 11 and this character “C” is written again in the address 4, whereafter addresses 12 and 5 are designated as the read address radr and the write address wadr, respectively.
Subsequently, as shown in FIG. 6, a character “A” is read out from the address 12 and this character “A” is written again in the address 5, whereafter addresses 13 and 6 are designated as the read address radr and the write address wadr, respectively.
As described above, based on the code words (Copy Pointer, Match Count=4 and Match Address=9), data is read out from the dictionary character by character (unit data) and thus read character is written again in other address of the dictionary, whereafter the next one character is read out and thereby the character string “ABCA” is decoded.
According to the related art, in the decoder circuit for decoding data compressed by using this LZ77 method, the read unit data is written again in the dictionary at one period of operation clock.
[Cited Patent Reference 1]: Republished Patent Application of International Publication Number W02003/032296 (pp. 12 to 13, FIGS. 3 and 4)